#include<iostream>
using namespace std;
void insertsort(int* a, int n)
{
	for (int i = 0; i < n-1; i++)
	{

		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{

				a[end + 1] = a[end];
				end--;


			}
			else
			{
				break;

			}
		}
		a[end + 1] = tmp;








	}




}
void popsort(int*a,int n)
{

	for (int i = 0; i < n - 1; i++)
	{
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (a[j] > a[j + 1])
			{
               std::swap(a[j], a[j + 1]);
			}




		}
	}





}
void selectsort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin <= end)
	{
		int mini = begin;
		int maxi = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (a[i] < a[mini])
			{

				mini = i;


			}
			if (a[i] > a[maxi])
			{
				maxi = i;
			}





		}
		swap(a[begin], a[mini]);
		if (begin == maxi)
		{
			maxi = mini;
		}
		swap(a[end], a[maxi]);
		begin++;
		end--;




	}








}
void sellsort(int*a,int n)
{
	int gap = 3;

	while (gap >= 1)
	{  
		for (int j = 0; j < gap; j++)
		{
			for (int i = j; i < n - gap; i+=gap)
			{
				int end = i;
				int tmp = a[end + gap];
				while (end >= 0)
				{
					if (tmp < a[end])
					{
						a[end + gap] = a[end];
						end -= gap;



					}
					else
					{
						break;


					}




				}
				a[end + gap] = tmp;













			}
		}
		gap /= 2;
	}






}


int main()
{
	int arr[] = { 2,6,1,9,3,7,8,6,5 };
	//insertsort(arr, sizeof(arr)/sizeof(arr[0]));
	//popsort(arr, sizeof(arr) / sizeof(arr[0]));
	//selectsort(arr, sizeof(arr) / sizeof(arr[0]));
	sellsort(arr, sizeof(arr) / sizeof(arr[0]));
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		cout << arr[i] << " ";

	}
	


}